package com.ln.prac.base.m202206.d16;

import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * <pre>
 *  TODO
 * </pre>
 *
 * @Author zhangj
 * @Date 2022/6/16 18:16
 */
public class SortTests {

    public static List<Integer> fastSort(List<Integer> list) {
        // 递归终止
        if(list.size() <= 1){
            return list;
        }

        var num = list.get(0);

        var left = list.stream().filter(x->x<num).collect(Collectors.toList());
        var mid = list.stream().filter(x-> x.equals(num)).collect(Collectors.toList());
        var right = list.stream().filter(x->x>num).collect(Collectors.toList());

        // 递归
        left = fastSort(left);
        right = fastSort(right);

        // 合并
        left.addAll(mid);
        left.addAll(right);

        return left;
    }


    /**
     * 快速排序 - 数组可变
     */
    public static void fastSort2(Integer[] A){
        fastSort2(A, 0, A.length);
    }

    public static void fastSort2(Integer[] A, int l, int r){
        // 递归中止
        if(r - l < 1) {
            return;
        }

        // 找到中间位置
        int mid = partition(A, l, r);

        // 递归
        fastSort2(A, l, mid);
        fastSort2(A, mid + 1,r);

        // 合并
        merge(A, l, mid, r);
    }

    private static void merge(Integer[] A, int l, int mid, int r) {
        // 设置哨兵，防止溢出
        Integer[] B = Arrays.copyOfRange(A, l, mid + 1);
        Integer[] C = Arrays.copyOfRange(A, mid, r + 1);
        B[B.length - 1] = C[C.length - 1] =  Integer.MAX_VALUE;

        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if(B[i] < C[j]) {
                A[k] = B[i++];
            } else {
                A[k] = C[j++];
            }
        }


    }

    private static int partition(Integer[] A, int l, int r) {
        int x = A[l];
        int i = l + 1, j = r;
        while (i != j) {
            if(A[i] < x) {
                ++i;
            } else {
                swap(A, i, --j);
            }
        }
        swap(A, i - 1, l);
        return i - 1;
    }

    private static void swap(Integer[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

    /**
     * 插入排序
     */
    public static void insertSort(Integer[] A) {
        for (int i = 1; i < A.length; i++) {
            int tmp = A[i];
            int j = i;
            for (; j > 0 && A[j - 1] > tmp ; j--) {
                A[j] = A[j - 1];
            }
            A[j] = tmp;
        }
    }


    /**
     * 冒泡排序
     */
    public static void bubbleSort(Integer[] A) {
        for (int i = A.length - 1; i > -1; i--) {
            for (int j = 0; j < i; j++) {
                if(A[j] > A[j + 1]) {
                    swap(A, j , j + 1);
                }
            }
        }
    }

    /**
     * 选择排序
     */
    public static void selectSort(Integer[] A) {
        for (int i = A.length - 1; i >= 0 ; i--) {
            int maxIndex = maxIndex(A, i + 1);
            swap(A, maxIndex, i);
        }
    }

    private static int maxIndex(Integer[] A, int i) {
        int max = Integer.MIN_VALUE;
        int index = 0;
        for (int k = 0; k < i; k++) {
            if(max < A[k]) {
                max = A[k];
                index = k;
            }
        }
        return index;
    }


    public static void main(String[] args) {
        Integer[] A = new Integer[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            A[i] = random.nextInt(100);
        }

//        System.out.println(fastSort(Arrays.asList(A)));

//        fastSort2(A);
//        System.out.println(Arrays.asList(A));

//        insertSort(A);
//        System.out.println(Arrays.asList(A));

//        bubbleSort(A);
//        System.out.println(Arrays.asList(A));

        selectSort(A);
        System.out.println(Arrays.asList(A));

    }

}
